//给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
//
//
// 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
//
//
// 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
//
// 以这种方式修改数组后，返回数组 可能的最大和 。
//
//
//
// 示例 1：
//
//
//输入：nums = [4,2,3], k = 1
//输出：5
//解释：选择下标 1 ，nums 变为 [4,-2,3] 。
//
//
// 示例 2：
//
//
//输入：nums = [3,-1,0,2], k = 3
//输出：6
//解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。
//
//
// 示例 3：
//
//
//输入：nums = [2,-3,-1,5,-4], k = 2
//输出：13
//解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 10⁴
// -100 <= nums[i] <= 100
// 1 <= k <= 10⁴
//
// Related Topics 贪心 数组 排序 👍 215 👎 0

package leetcode.editor.cn;

import java.util.Arrays;

@SuppressWarnings("all")
//Java：K 次取反后最大化的数组和
class K次取反后最大化的数组和 {
    public static void main(String[] args) {
        Solution solution = new K次取反后最大化的数组和().new Solution();
        // TO TEST
        int[] nums = {4, -5, 4, -5, 9, 4, 5};
        System.out.println(solution.largestSumAfterKNegations(nums, 1));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int largestSumAfterKNegations(int[] nums, int k) {


            heapfy(nums);
            int i;
            for (i = k; i > 0; i--) {
                if (nums[0] < 0) {
                    nums[0] = -nums[0];
                    siftDown(nums, 0, nums[0]);
                } else
                    break;
            }
            if (i % 2 == 0)
                return Arrays.stream(nums).sum();

            nums[0] = -nums[0];
            return Arrays.stream(nums).sum();
        }

        /**
         * 构造逻辑小顶堆
         *
         * @param nums 逻辑堆
         * @param size 逻辑容量
         */
        private void heapfy(int[] nums) {
            for (int i = (nums.length >> 1) - 1; i >= 0; i--) {
                siftDown(nums, i, nums[i]);
            }
        }

        private void siftDown(int[] nums, int k, int e) {

            int half = nums.length >> 1;
            while (k < half) {
                int child = (k << 1) + 1;//左孩子索引
                if (child + 1 < nums.length &&
                        nums[child + 1] < nums[child])//找最高优先级的孩子
                    child++;

                if (nums[child] >= e)//孩子优先级不够,下浮失败
                    break;

                // 下浮
                nums[k] = nums[child];
                k = child;
            }
            nums[k] = e;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)


}
